package com.example.demo.listnode;

import com.example.demo.model.ListNode;
import org.junit.jupiter.api.Test;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 删除链表的倒数第 N 个结点
 */
public class RemoveNthFromEnd {

    @Test
    public void test() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        listNode1.setNext(listNode2);
        listNode2.setNext(listNode3);
        listNode3.setNext(listNode4);
        listNode4.setNext(listNode5);

        ListNode node = removeNthFromEnd(listNode1, 5);

        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = getLength(head);

        ListNode node = new ListNode(0, head);

        head = node;
        for (int i = 0; i < len - n; i++) {
            head = head.next;
        }

        head.next = head.next.next;
        return node.next;
    }

    /**
     * 双指针
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode node0 = new ListNode(0, head);

        ListNode first = head;
        ListNode second = node0;

        for (int i = 0; i < n; ++i) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;
        return node0.next;
    }

    /**
     * 栈
     */
    public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode node0 = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();

        ListNode tmp = node0;
        while (tmp != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }

        for (int i = 0; i < n; ++i) {
            stack.pop();
        }

        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return node0.next;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}
